package com.whosly.demo.benchmark.sortalgorithms.radix;

import com.whosly.demo.benchmark.sortalgorithms.ISortingAlgorithms;

import java.util.ArrayList;
import java.util.List;

/**
 * 基数排序（Radix Sort）， 支持负数排与正数的混合排序
 *
 * @author fengyang
 * @date 2023/6/13 下午2:42
 * @see <a href="fengyang@stoneatom.com">mailTo: fengyang@stoneatom.com</a>
 */
public class RadixSort implements ISortingAlgorithms
{
    @Override
    public int[] sorting(int[] arr)
    {
        if (arr.length < 2) {
            return arr;
        }

        //求出最大值 maxVal, 最小值 minVal
        int maxVal = arr[0];
        int minVal = 0;
        for (int a : arr) {
            if (maxVal < a) {
                maxVal = a;
            }
            if(minVal > a){
                minVal = a;
            }
        }

        //获取数组中最多有多少位数字， 也就是求出最大值位数 n
        //由于有了负数的存在，那么最大值的位数需要改变，因为下面的将数组化为整数的时候，最大值要改变，
        //所以此时含有负数的数组化为非负整数的时候，最大值发生了改变，为max - min，
        //如果数组是非负整数，因为下面的将数组化为整数的时候，最大值要改变
        //所以此时的最大值还是max - min
        int max = maxVal - minVal;
        int n = 1;
        while (max / 10 != 0) {
            max /= 10;
            n++;
        }

        // 进行基数排序
        getRadixSort(arr, n, minVal);

        return arr;
    }

    private void getRadixSort(int[] arr, int total,int min){
        if(total <= 0){
            return;
        }

        for (int i = 0; i < total; i++) {
            //定义一个二维数组或者列表结构 radix， 内部的List用于统计每个数位出现的次数
            // 定义为 Long 类型的原因是因为会有值的相加，int 可能越界
            List<List<Long>> radix = new ArrayList<>();

            // radix 初始化
            for (int j = 0; j < 10; j++) {
                radix.add(new ArrayList<>());
            }

            int index;
            for (int a : arr) {
                // 注意这里要是arr[i] - min，以防止负数的存在
                long tempVal = (long) a - min;
                // Math.pow(底数,几次方) 如：int a=3; int b=6; int c=Math.pow(a,b); 就是a^b, 3的6次方
                index = (int) ((tempVal / (int) Math.pow(10, i)) % 10);

                // 将数组中的值赋值到有序数组中
                radix.get(index).add(tempVal);
            }

            index = 0;
            for (List<Long> list : radix) {
                for (long a : list) {
                    // 因为防止有负数，本来将数组的值都减去了min,所以要变成原来的数组，要将所有的数字都加上min才可以
                    int val = (int) (a + min);
                    arr[index++] = val;
                }
            }
        }
    }
}
